import java.util.*;

/**
 * Created by zhangjinrui on 17/6/27.
 */

public class Solution332 {

    public static void main(String args[]) {
        Solution332 s = new Solution332();
        System.out.println(s.findItinerary(new String[][]{{"JFK", "ABC"}, {"JFK", "BBC"}, {"BBC", "JFK"}}));
    }

    HashMap<String, List<String>> mp;
    HashMap<String, Integer> mp2;
    List<String> ret = null;
    int n;
    public List<String> findItinerary(String[][] tickets) {
        n = tickets.length;
        mp = new HashMap<>();
        mp2 = new HashMap<>();
        for (String[] edge : tickets) {
            String from = edge[0];
            String to = edge[1];
            mp2.put(from, 1);
            mp2.put(to, 1);
            if (!mp.containsKey(from)) {
                mp.put(from, new LinkedList<>());
            }
            mp.get(from).add(to);
        }
        for (List<String> tos : mp.values()) {
            Collections.sort(tos);
        }
        List<String> tres = new LinkedList<>();
        tres.add("JFK");
        dfs(tres, "JFK");
        return ret;
    }

    public void dfs(List<String> res, String s) {
        if (!mp.containsKey(s) || mp.get(s).isEmpty()) {
            if (satisfied(res)) {
                ret = res;
            }
            return;
        }

        if (mp.containsKey(s)) {
            for (int i = 0; i < mp.get(s).size(); i++) {
                String next = mp.get(s).get(i);
                mp.get(s).remove(i);
                res.add(next);
                dfs(res, next);
                if (ret != null) {
                    return;
                }
                res.remove(res.size() - 1);
                mp.get(s).add(i, next);
            }
        }
    }

    public boolean satisfied(List<String> ret) {
//        HashMap<String, Integer> tmp = new HashMap<>();
//        for (String s : ret) {
//            tmp.put(s, 1);
//        }
        return ret.size() == n + 1;
    }

//    Map<String, PriorityQueue<String>> flights;
//    LinkedList<String> path;
//
//    public List<String> findItinerary(String[][] tickets) {
//        flights = new HashMap<>();
//        path = new LinkedList<>();
//        for (String[] ticket : tickets) {
//            flights.putIfAbsent(ticket[0], new PriorityQueue<>());
//            flights.get(ticket[0]).add(ticket[1]);
//        }
//        dfs("JFK");
//        return path;
//    }
//
//    public void dfs(String departure) {
//        PriorityQueue<String> arrivals = flights.get(departure);
//        while (arrivals != null && !arrivals.isEmpty())
//            dfs(arrivals.poll());
//        path.addFirst(departure);
//    }

}
